/*
    Alunos:
        Jorge Luis Stefanelli Bonafé	5889794
        Marcelo Koti Kamada             7277670
*/

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <values.h>

const int INF = MAXINT/2;

// imprime a matriz na saida padrao
void imprime_matriz(int **matriz, int n, int m) {
    int i, j;
    for(i = 0; i < n; i++) {
        for(j = 0; j < m; j++)
            printf("%d ", matriz[i][j]);
        printf("\n");
    }
}

void floyd_warshall(int **matriz, int n) {
    int i, j, k;
    for(k = 0; k < n; k++)
        for(i = 0; i < n; i++)
            if(i != k && matriz[i][k] < INF)
                for(j = 0; j < n; j++)
                    if(matriz[i][j] > matriz[i][k] + matriz[k][j])
                        matriz[i][j] = matriz[i][k] + matriz[k][j];
}

void free_matrix(int **matriz, int n) {
    int i;
    for(i = 0; i < n; i++)
        free(matriz[i]);
    free(matriz);
}

int main(int argc, char *argv[]) {
    int n;  // numero de juncoes 2 <= n <= 200
    int m;  // numero de ruas    n-1 <= m <= (n(n-1))/2

    int A;  // juncao A e' conectada a
    int B;  // juncao B
    int W;  // com comprimento de rua W

    scanf("%d%d", &n, &m);  // entra com o numero de juncoes e o numero de ruas

    assert(2 <= n && n <= 1000);             // o numero de juncoes deve estar entre 2 e 200
    assert(n-1 <= m && m <= (n*(n-1))/2);   // o numero de ruas deve estar entre n-1 e (n(n-1))/2

    int **matriz = (int**) malloc(sizeof(int*)*n);   // aloca matriz de distancias
    assert(matriz != NULL);                         // se a alocacao foi bem sucedida

    int i, j;
    for(i = 0; i < n; i++) {
        matriz[i] = (int*) malloc(sizeof(int)*n);   // cada linha da matriz e' uma juncao, e as colunas sao as distancais para a outra juncao
        assert(matriz[i] != NULL);                  // verifica a alocacao
    }

    // inicializa a matriz com distancias infinitas ate as outras juncoes, pq ainda nao sabemos quais as distancias
    for(i = 0; i < n; i++)
        for(j = 0; j < n; j++) {
            matriz[i][j] = INF;
            //printf("%d %d\n", i, j);
        }

    // leitura das distancias W entre as juncoes A e B
    for(i = 0; i < m; i++) {
        scanf("%d%d%d", &A, &B, &W);    // leitura de A, B e W
        A--;                            // decrementa A e B
        B--;                            // porque a matriz comeca do zero, e na entrada as juncoes comecam do um
        assert(A < n && B < n);         // verifica se os indices estao dentro da matriz
        matriz[A][B] = W;               // atribui tanto a A para B, quanto de B para A
        matriz[B][A] = W;               // porque as ruas sao ambos os sentidos
    }

#ifdef DISPLAY_MATRIX
    printf("antes do floyd_warshall\n");
    imprime_matriz(matriz, n, n);
#endif

    // roda o algoritimo de Floyd-Warshall, para calcular as distancias
    floyd_warshall(matriz, n);

    int *distancias_maximas = (int*) calloc(n, sizeof(int));

    for(i = 0; i < n; i++) {        // monta o vetor distancias_maximas que tem
        for(j = 0; j < n; j++)      // as maiores distancias de cada juncao
            if(i != j && distancias_maximas[i] < matriz[i][j])
                distancias_maximas[i] = matriz[i][j];
       //printf("distancias_maximas[%d]: %d\n", i, distancias_maximas[i]);
    }

    int index = 0;
    int max = INF;
    for(i = 0; i < n; i++) {                    // pega a menor das maiores distancias
        if(max > distancias_maximas[i]) {
            max = distancias_maximas[i];
            index = i;
        }
    }

#ifdef DISPLAY_MATRIX
    printf("depois do floyd-warshall\n");
    imprime_matriz(matriz, n, n);
#endif

    //printf("juncao %d com distancia %d\n", index, max);
    printf("%d\n", max);

    // desaloca matriz
    free_matrix(matriz, n);

    return 0;
}

